package 腐烂的苹果;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param grid int整型ArrayList<ArrayList<>>
     * @return int整型
     */
    static int N = 1010, n, m, ans;

    static ArrayList<ArrayList<Integer>> g = new ArrayList<>();
    static boolean[][] st = new boolean[N][N];
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static Queue<PII> q = new LinkedList<>();
    static Queue<PII> tmp = new LinkedList<>();

    public int rotApple(ArrayList<ArrayList<Integer>> grid) {
        g = grid;
        n = g.size();
        m = g.get(0).size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g.get(i).get(j) == 2) {
                    q.offer(new PII(i, j));
                }
            }
        }
        while (ans++ > 0) {
            if (q.isEmpty()) {
                break;
            }
            while (!q.isEmpty()) {
                f(q.poll());
            }
            while (!tmp.isEmpty()) {
                q.offer(tmp.poll());
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g.get(i).get(j) == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }

    private void f(PII start) {
        st[start.x][start.y] = true;
        for (int i = 0; i < 4; i++) {
            int x = dx[i] + start.x, y = dy[i] + start.y;
            if (x < 0 || x >= n || y < 0 || y >= n) {
                continue;
            }
            if (st[x][y]||g.get(x).get(y) == 0) {
                continue;
            }
            if (g.get(x).get(y) == 1) {
                g.set(x, g.get(x)).set(y, 2);
                tmp.offer(new PII(x, y));
            }
        }

    }
}

class PII {
    int x, y;

    public PII(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
